The present invention relates to a Reed Solomon coding apparatus and a Reed Solomon coding method for correcting multiple errors, which are widely used in error correction of digital signal processing.
As codes which enable multiple error correction for storage information in a variety of mass storages, transmission information in high-speed communication, and the like, Reed Solomon codes are widely used.
The Reed Solomon code is a code on a Galois field which contains roots xcex1 of P(x) (primitive polynomial)=0 as primitive elements, and is known as one type of block error-correcting code.
Consider a Reed Solomon code of a code length n=2mxe2x88x921 assuming that t is the number of errors to-be-corrected, m is a degree of an extended field, and primitive elements of a Galois field GF (2m) are a xcex10, xcex1, . . . xcex12mxe2x88x922. According to this code, m bits is a processing unit, i.e., a symbol. The amount of original information is (nxe2x88x922t) symbols. In description below, suppose that m=8 and one symbol is represented as 8 bits (1 byte). A receiving word of one packet is composed of n symbols. The number of symbols xe2x80x9cnxe2x80x9d is called a code length. When t=8, the Reed Solomon code is capable of correcting eight symbol errors. The original information in the receiving word, i.e., the (nxe2x88x922t) symbols are called an information word and 2t symbols added to correct errors are called a check word.
The Reed Solomon coding apparatus is adapted to add the check word of 2t symbols to the information word of (nxe2x88x922t)symbols so as to generate a codeword comprising a symbol sequence of a code length n.
A description will be given of an algorithm for a coding process of the Reed Solomon code (hereinafter referred to as an RS code).
First, a primitive polynomial will be described as a first element for determining the RS code.
In case of m=8, 255 primitive elements, i.e., xcex10-xcex1254 are present in the Galois field, and vector values of respective primitive elements are determined by a primitive polynomial P(z).
In general, when m=8, the primitive polynomial P(x) is expressed as:
P(x)=x5+x4+x3+x2+1.
In this case, vector values for the respective primitive elements are:
xcex10=00000001, xcex11=00000010, xcex12=00000100,
xcex13=00001000, xcex14=00010000, xcex15=00100000,
xcex16=1000000, xcex17=10000000, xcex18=00011101,
xcex1900111010 . . . .
Here, how these vector values are determined will be explained. When m=8, each of the vector values is represented as 8 bits. In xcex10 to xcex17, as a degree increases one by one, bit-shifting is performed to the left. xcex18 is calculated by assigning xcex1 to the primitive polynomial P(x) and assuming that P(xcex1)=0, and this is expressed as:
P(xcex1)=xcex18+xcex14+xcex13+xcex12+1=0
Since addition and subtraction are the same in Galois operation, P(xcex1)=xcex18+xcex14+xcex13+xcex12+1=0 is expressed as:
xcex18=xcex14+xcex13+xcex12+1
Therefore, xcex18=00011101, and xcex19 is obtained by bit-shifting xcex18 to the left.
Thus, the primitive elements have vector values determined according to a rule, where bit-shifting is performed to the left as the degree increases, and when the most significant bit is xe2x80x9c1xe2x80x9d, the corresponding vector value is bit-shifted to the left, and then xcex1mxcex18=00011101 is added to generate a vector value of a subsequent degree. It should be noted that addition in Galois operation corresponds to an exclusive-OR(XOR) addition of respective vector values.
The RS code is a code on the Galois field, and is determined by operation using primitive elements (255 primitive elements when m=8). Hence, if each of the primitive elements has different vector values, then different codes are obtained even if the same operational procedure is used. In other words, if different primitive polynomials are used, different RS codes are obtained.
Subsequently, a description will be given of a generator polynomial as a second element for determining the RS code.
The RS code for correcting xe2x80x9ctxe2x80x9d errors is generated in the following way. Express (nxe2x88x922t) original information as input data in information polynomial form, and find a remainder polynomial resulting from dividing the information polynomial by a generator polynomial shown below. Then, to the (nxe2x88x922t) original information data (information word), the check word of the 2t symbols calculated as the remainder polynomial is added to generate the RS code of the code length n.
The general form of the generator polynomial for the RS code for correcting the multiple errors (nxe2x89xa62mxe2x88x921, the number of errors to-be-corrected is t, and a minimum distance dminxe2x89xa62t+1) is:                                                                         G                ⁡                                  (                  x                  )                                            =                              xe2x80x83                            ⁢                                                (                                      x                    -                                          α                      n                                                        )                                ⁢                                  (                                      x                    -                                          α                      1                                                        )                                ⁢                                  (                                      x                    -                                          α                      2                                                        )                                ⁢                                  xe2x80x83                                ⁢                …                ⁢                                  xe2x80x83                                ⁢                                  (                                      x                    -                                          α                                                                        2                          ⁢                          t                                                -                        1                                                                              )                                                                                                        =                              xe2x80x83                            ⁢                                                ∏                                      i                    =                    0                                                                              2                      ⁢                      t                                        -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  (                                      x                    -                                          α                      1                                                        )                                                                                                        =                              xe2x80x83                            ⁢                                                x                                      2                    ⁢                    t                                                  +                                                      c                                                                  2                        ⁢                        t                                            -                      1                                                        ⁢                                      x                                                                  2                        ⁢                        t                                            -                      1                                                                      +                                                      c                                                                  2                        ⁢                        t                                            -                      2                                                        ⁢                                      x                                                                  2                        ⁢                        t                                            -                      2                                                                      +                                                      c                                                                  2                        ⁢                        t                                            -                      3                                                        ⁢                                      x                                                                  2                        ⁢                        t                                            -                      3                                                                      +                                  …                  ⁢                                      xe2x80x83                                    ⁢                                      c                    2                                    ⁢                                      x                    2                                                  +                                                                                                        xe2x80x83                            ⁢                                                                    c                    1                                    ⁢                  x                                +                                  c                  0                                            ⁢                              xe2x80x83                                                                        (        1        )            
xe2x80x9ckxe2x80x9d information data, akxe2x88x921 akxe2x88x922 . . . a2, a1, a0 are expressed by means of the following information polynomial:
xe2x80x83I(x)=akxe2x88x921xnxe2x88x921+akxe2x88x922xnxe2x88x922+ . . . +a1x2t+1+a0x2t . . . xe2x80x83xe2x80x83(2)
The expression (2) is divided by the expression (1), resulting in a remainder polynomial R(x), which becomes a check polynomial, xe2x80x9c2txe2x80x9d coefficients of which become the check word. This is summarized as:
I(x)=Q(x)G(x)+R(x) (I(x): information polynomial, G(x): generator polynomial, Q(x): quotient polynomial, R(x): remainder polynomial)
In the Galois operation, addition and subtraction are the same as described above, and therefore,
R(x)=Q(x)G(x)+I(x)=: b2txe2x88x921x2txe2x88x921+b2txe2x88x92tx2txe2x88x922+b2txe2x88x923x2txe2x88x923+ . . . +b1x+b0
Therefore, the whole coded polynomial X (x) is expressed as:
X(x)=I(x)+R(x)=akxe2x88x921xnxe2x88x921+akxe2x88x922xnxe2x88x922+ . . . +a1x2t+1+a0x2t+b2txe2x88x921x2txe2x88x921+b2txe2x88x92tx2txe2x88x92t+ . . . +b1x+b0 . . . xe2x80x83xe2x80x83(3)
In this expression (3), n coefficients, i.e., akxe2x88x921, akxe2x88x922, a2, a1, a0, b2txe2x88x922, . . . b1, b0 become the RS code.
As concerns an initial value xe2x80x9cixe2x80x9d of the generator polynomial (1), in case of an RS code for transmission in a communication system, i=0 is generally adopted, wile in case of an RS code in a disc system, i=120 is generally adopted.
Depending upon the initial value xe2x80x9cixe2x80x9d, coefficients C of an expanded expression (1) vary, and thereby coefficients b of the remainder polynomial vary. Hence, like the primitive polynomial, when a different generator polynomial is used, a different RS code is generated even if the same procedure is used.
Subsequently, a description will be given of implementation of an RS coding algorithm as hardware.
The RS code is composed of the information word comprising coefficients of the information polynomial and the check word comprising coefficients of the remainder polynomial obtained by dividing the information polynomial by the generator polynomial.
When finding the remainder polynomial, in order to sequentially divide the coefficients of the information polynomial by the coefficients of the generator polynomial, it is necessary that multiplication and addition be performed using the coefficients of the information polynomial and the coefficients of respective degrees of the generator polynomial. Conventionally, hardware for implementing this division is generally constituted by Galois field multipliers and Galois field adders for performing operation on the coefficients (fixed values) of respective degrees of the generator polynomial and the coefficients of the information polynomial, and shift registers for holding operation results.
FIG. 6 is a block diagram showing a structure of an error-correcting code creating circuit in a conventional RS coding apparatus disclosed in Japanese Patent No. 2591611. Coefficients of an information polynomial as input data are sent to a register 605 in a final stage, and then multiplication results of a coefficient of a highest degree of the information polynomial and respective coefficients g0-g2txe2x88x921 are output from product circuits 611-615, i.e., multipliers, to be added to the coefficient values of the information polynomial stored in the registers 601-605, respectively. This makes one division and moves the content stored in each of the registers 601-605 one by one. This division is sequentially repeated to find a quotient polynomial, and values remaining in the registers 601-604 without being transferred to the register 605 become coefficients of a remainder polynomial.
As the coefficients of the generator polynomial, prefound fixed values are used. For this reason, as the multipliers for performing Galois field multiplication on the coefficients of the generator polynomial and the coefficients of the information polynomial, fixed-value multipliers called xe2x80x9ccoefficient unitsxe2x80x9d are used. The coefficient units implement multiplication by bit-shift operation, because the RS code is a cyclic code.
However, the rule of the bit-shift operation by the coefficient units is determined by the primitive polynomial. Specifically, this is determined by xcex1m, Therefore, when the same fixed-value multiplication is performed but a different primitive polynomial is used, bit-shift operation must be changed. For this reason, if the primitive polynomial is changed, the corresponding error-correcting code cannot be created. In this case, in order to create the error-correcting code, coefficient units adapted to the corresponding primitive polynomial and a multiplier including the same needs to be provided.
In addition, the initial value xe2x80x9cixe2x80x9d of the generator polynomial (1) varies from system to system. As mentioned previously, in the communication system, i=0 or 1 is commonly used, while in the disc system, i=120 is commonly used. The coefficients C of the respective degrees of the generator polynomial (1) have fixed values when the initial value xe2x80x9cixe2x80x9d is fixed, whereas if the xe2x80x9cixe2x80x9d changes, then the fixed values of the coefficient values C are changed. Therefore, if the generator polynomial is changed, coefficients of respective degrees adapted to the corresponding generator polynomial need to be provided. However, conventionally, coefficient values of the generator polynomial are prefound, and division of the information polynomial is performed using these values, which makes it impossible to create the error-correcting code if a different generator polynomial is used.
Further, when the number of errors to-be-corrected is changed, it is required that the number of stages in the error-correcting code creating circuit be correspondingly changed. For instance, assuming that the number of errors is reduced by one in the example shown in FIG. 6, the number of stages needs to be set to (2txe2x88x922). The number of stages cannot be changed in the conventional RS coding apparatus including the error-correcting code creating circuit shown in FIG. 6, and thereby the number of errors to-be-corrected cannot be changed.
Thus, in the conventional Reed Solomon coding apparatus and Reed Solomon coding method, although operation is carried out using the same algorithm and the same procedure, the RS coding process cannot be performed if the primitive polynomial, the generator polynomial, or the number of errors to-be-corrected is changed. If handling a case where the primitive polynomial, the generator polynomial, or the number of errors to-be-corrected is changed, it becomes extremely difficult to share the hardware, and therefore the coefficient units according to these changes need to be provided, resulting in a large-scale circuit. For this reason, an RS encoder for one type of primitive polynomial and generator polynomial has been very commonly used.
It is an object of the present invention to provide a Reed Solomon coding apparatus and a Reed Solomon coding method which are capable of performing a Reed Solomon coding process in a way adapted to a case where a primitive polynomial, a generator polynomial, and the number of errors to-be-corrected are changed.
Other objects and advantages of the present invention will become apparent from the detailed description given hereinafter. It should be understood, however, that the detailed description and specific embodiment are given by way of illustration only, since various changes and modifications within the scope of the invention will become apparent to those skilled in the art from this detailed description.
According to a first aspect of the present invention, a Reed Solomon coding apparatus comprises: generator polynomial coefficient generation means which receives a generator initial value corresponding to a primitive element with a minimum power of roots corresponding to powers of a which are obtained by setting a generator polynomial to be zero, and a primitive polynomial set value corresponding to a value of an xcex1m, when a degree of an extended field is m (mxe2x89xa71 m: integer) and one of primitive elements is xcex1, as inputs, and expands the generator polynomial according to change of at least one of the generator initial value and the primitive polynomial set value to generate coefficient data comprising coefficients of respective degrees; and data coding means which receives information data and the coefficient data as inputs, divides the information data by the coefficient data according to change of either the, generator initial value or the primitive polynomial set value to obtain remainder data, arid couples the remainder data and the information data to form Reed-Solomon coded data. Therefore, when the primitive polynomial or the generator polynomial is changed, the generator initial value or the primitive polynomial set value adapted to the corresponding polynomial is input. Thereby, it is possible to provide a Reed Solomon coding apparatus in which the generator polynomial is expanded to generate coefficient data comprising coefficients of respective degrees and a Reed solomon coding process is performed for the information data in a way adapted to a case where the primitive polynomial or the generator polynomial is changed.
According to a second aspect of the present invention, the generator polynomial coefficient generation means and the data coding means each comprises a plurality of multipliers, and the multipliers each comprises coefficient units serially connected in (mxe2x88x921) stages, the coefficient units each performing multiplication on the primitive element a by using combination of a bit-shifted primitive element a and an exclusive-OR of the bit-shifted primitive element a and the primitive polynomial set value xcex1m. Therefore, when the primitive polynomial is changed, the corresponding primitive polynomial set value is input, whereby Galois multiplication is performed according to a new primitive polynomial. Thereby, it is possible to provide a Reed Solomon coding apparatus which is capable of performing a Reed Solomon coding process in a way adapted to a case where the primitive polynomial is changed.
According to a third aspect of the present invention, the coefficient units each outputs a vector value obtained by shifting a vector value of the generator initial value by one bit to the left every time it performs multiplication on the primitive element xcex1, and when the most significant bit is 1, the coefficient unit outputs an exclusive-OR of the bit-shifted primitive element xcex1 and the primitive polynomial set value xcex1m when the corresponding degree increases. Therefore, when the primitive polynomial is changed, the corresponding primitive polynomial set value is input, whereby Galois multiplication is performed according to a new primitive polynomial. Thereby, it is possible to provide a Reed Solomon coding apparatus which is capable of performing a Reed Solomon coding process in a way adapted to a case where the primitive polynomial is changed.
According to a fourth aspect of the present invention, the generator polynomial coefficient generation means comprises, when a number of errors to be corrected is t (txe2x89xa71 t: integer): a 2t-th multiplier which repeats multiplication by the primitive element xcex1 with respect to the generator initial value, and outputs a multiplication result for each multiplication; a 0th multiplier which performs multiplication on the generator initial value and the multiplication result of the 2t-th multiplier, and then repeats multiplication on the resulting multiplication result and the multiplication result of the 2t-th multiplier; a 0th register which updates and holds output data of the 0-th multiplier: a first adder which receives output data of the 0-th register on one input and performs addition on two inputs; a first register which updates and holds output data of the first adder; a first multiplier which performs multiplication on output data of the first register and output data of the 2t-th multiplier and outputs a multiplication result to the other input of the first adder; an N-th adder which receives output data of an (Nxe2x88x921)-th register (2txe2x88x921xe2x89xa7Nxe2x89xa72 N : integer) on one input, and performs addition on two inputs: an N-th register which updates and holds output data of the N-th adder; and an N-th multiplier which performs multiplication on output data of the N-th register and output data of the 2t-th multiplier, and outputs a multiplication result to the other input of the N-th adder, wherein data held in the 0-th to (2txe2x88x921)-th registers are output as coefficient data of the generator polynomial. Therefore, when the generator polynomial is changed, the corresponding generator initial value is input, whereby a new generator polynomial is expanded to generate coefficient data. Thereby, it is possible to provide a Reed Solomon coding apparatus which is capable of performing a Reed Solomon coding process in a way adapted to a case where the generator polynomial is changed.
According to a fifth aspect of the present invention, the data coding means comprises, when a number of errors to be corrected is t (txe2x89xa71 t: integer) a 0th multiplier which performs multiplication on a value of a 0th degree of the coefficient data of the generator polynomial and the information data; a 0th register which holds output data of the 0th multiplier; an R-th multiplier which performs multiplication on a value of an R-th degree (2txe2x88x922xe2x89xa7Rxe2x89xa71) of the coefficient data of the generator polynomial and the information data; an (Rxe2x88x921)-th adder which performs addition on output data of the R-th multiplier and data held in an (R-1)-th register; an R-th register which holds output data of the (Rxe2x88x921)-th adder; a (2t-1)-th multiplier which performs multiplication on a value of a (2t-1)-th degree of the coefficient data of the generator polynomial and the information data; a (2txe2x88x922)-th adder which performs addition on output data of the (2txe2x88x921)-th multiplier and data held in a (2txe2x88x922)-th register; a (2txe2x88x921)-th register which holds on output data of the (2txe2x88x922)-th adder; and a (2txe2x88x921)-th adder which performs addition on output data of the (2txe2x88x921)-th register and the information data. Thereby, it is possible to provide a Reed Solomon coding apparatus which is capable of performing a Reed Solomon coding process in a way adapted to a case where the primitive polynomial is changed.
According to a sixth aspect of the present invention, the coefficient unit comprises registers which shift bits other than the most significant bit of the input data to be multiplied and hold bit-shifted data, and add zero as the lowest data to the bit-shifted data and output addition data; and a selector which receives the most significant bit of the input data as an input, and selects and outputs an exclusive-OR of the primitive polynomial set value and output data of the registers when the most significant bit is 1, and selects and outputs the output data of the registers when the most significant bit is zero. Thereby, it is possible to provide a Reed Solomon coding apparatus which is capable of performing a Reed Solomon coding process in a way adapted to a case where the primitive polynomial is changed.
According to a seventh aspect of the present invention, the generator polynomial coefficient generation means receives a number t of errors to be corrected as an input and expands the generator polynomial according to change of the number t, to generate coefficient data comprising coefficients of respective degrees, and the data coding means receives the number t as an input and divides the information data according to change of the number t. Therefore, it is possible to provide a Reed Solomon coding apparatus in which the generator polynomial is expanded and the information data is divided to obtain remainder data according to change of the number t of errors to-be-corrected, and thereby the Reed Solomon coding process is performed according to change of the number t.
According to an eighth aspect of the present invention, the data coding means comprises, when a maximum number of errors to be corrected is s (sxe2x89xa7t s: integer): a 0th multiplier which performs multiplication on a value of a 0th degree of the coefficient data of the generator polynomial and the information data; a 0th register which holds output data of the 0th multiplier; a (2Mxe2x88x921)-th multiplier which performs multiplication on a value of a (2Mxe2x88x921)-th (sxe2x88x921xe2x89xa7Mxe2x89xa71 M: integer) of the coefficient data of the generator polynomial and the information data; a 2M-th multiplier which performs multiplication on a value of a 2M-th degree of the coefficient data of the generator polynomial and the information data; a (2Mxe2x88x921)-th adder which performs addition on output data of the 2M-th multiplier and data held in a (2Mxe2x88x921)-th register; a 2M-th selector which selects one of output data of the (2Mxe2x88x921)-th adder and output data of the 2M-th multiplier; a 2M-th register which holds output data of the 2M-th selector; a (2sxe2x88x921)-th multiplier which performs multiplication on a value of a (2sxe2x88x921)-th degree of the coefficient data of the generator polynomial and the information data; a (2sxe2x88x922)-th adder which performs addition on output data of the (2sxe2x88x921)-th multiplier and data held in the (2sxe2x88x922)-th register; and a (2sxe2x88x921)-th register which holds output data of the (2sxe2x88x922)-th adder, wherein a (2(sxe2x88x92t))-th selector selects output data of a (2(sxe2x88x92t))-th multiplier, with respect to the number t of errors to be corrected. Therefore, it is possible to provide a Reed Solomon coding apparatus which is capable of a Reed Solomon coding process according to change of the number t of errors to-be-corrected.
According to a ninth aspect of the present invention, in a Reed Solomon coding method, a generator initial value corresponding to a primitive element with a minimum power of roots corresponding to powers of a which are obtained by setting a generator polynomial to be zero, and a primitive polynomial set value corresponding to a value of an xcex1m, when a degree of an extended field is m (mxe2x89xa71 m: integer) and one of primitive element is xcex1, are received as inputs, and the generator polynomial is expanded according to change of at least one of the generator initial value and the primitive polynomial set value, to generate coefficient data comprising coefficients of respective degrees; and information data and the coefficient data are received as inputs, the information data is divided by the coefficient data according to change of either the generator initial value or the primitive polynomial set value to obtain remainder data, and the remainder data and the information data are coupled to form Reed-Solomon coded data. Therefore, when the primitive polynomial or the generator polynomial is changed, the generator initial value or the primitive polynomial set value adapted to the corresponding polynomial is input. Thereby, it is possible to provide a Reed Solomon coding method which is capable of a Reed Solomon coding process in a way adapted to a case where the primitive polynomial or the generator polynomial is changed.
According to a tenth aspect of the present invention, the generator polynomial is expanded according to change of an input number t of errors to be corrected (txe2x89xa71 t: integer), and the information data is divided according to change of an input number t. Therefore, it is possible to provide a Reed Solomon coding method which is capable of a Reed Solomon coding process according to change of the number t of errors to-be-corrected.